// export class Sudo {
//   static test() {
//     let board = [
//       0, 2, 0, 0, 0, 8, 0, 9, 0, 0, 0, 0, 4, 9, 0, 5, 0, 0, 0, 9, 3, 1, 0, 0, 8,
//       0, 0, 0, 0, 0, 0, 8, 2, 0, 0, 0, 0, 0, 0, 5, 0, 0, 1, 6, 8, 0, 0, 0, 6, 1,
//       0, 2, 0, 7, 0, 0, 8, 0, 0, 0, 0, 1, 3, 9, 0, 6, 0, 0, 1, 0, 8, 0, 0, 5, 1,
//       8, 0, 0, 0, 0, 0,
//     ];
//   }
//   static getResult(board: Array<number>) {
//     let index = (x: number, y: number) => {
//       return x + y * 9;
//     };
//     let dump = () => {
//       let str = "";
//       for (let j = 0; j < 9; j++) {
//         for (let i = 0; i < 9; i++) {
//           str += board[index(i, j)];
//         }
//         str += "\n";
//       }
//     };
//     let getValid = (x: number, y: number) => {
//       let ret = [1, 2, 3, 4, 5, 6, 7, 8, 9];
//       let ind = -1;
//       for (let i = 0; i < 9; i++) {
//         ind = ret.indexOf(board[index(i, y)]);
//         if (ind != -1) ret.splice(ind, 1);
//       }
//       for (let j = 0; j < 9; j++) {
//         ind = ret.indexOf(board[index(x, j)]);
//         if (ind != -1) ret.splice(ind, 1);
//       }
//       let areaX = Math.floor(x / 3);
//       let areaY = Math.floor(y / 3);
//       for (let i = 0; i < 3; i++) {
//         for (let j = 0; j < 3; j++) {
//           ind = ret.indexOf(board[index(i + areaX * 3, j + areaY * 3)]);
//           if (ind != -1) ret.splice(ind, 1);
//         }
//       }
//       return ret;
//     };

//     let loopTimes = 0;
//     let resu = (ind: number) => {
//       loopTimes++;
//       let y = ind % 9;
//       let x = (ind - y) / 9;
//       if (ind >= 81) return true;
//       if (board[index(x, y)] != 0) return resu(ind + 1);

//       let validNums = getValid(x, y);
//       for (let i = 0; i < validNums.length; i++) {
//         let n = validNums[i];
//         board[index(x, y)] = n;
//         // dump()
//         if (resu(ind + 1) == true) return true;
//         else board[index(x, y)] = 0;
//       }
//     };
//     dump();
//     resu(0);
//     dump();
//     // console.log("loopTimes : " + loopTimes);
//     return board;
//   }
// }

// const isValid = (
//   col: number,
//   row: number,
//   val: string,
//   board: string[][]
// ): boolean => {
//   let n: number = board.length;
//   // 列向检查
//   for (let rowIndex = 0; rowIndex < n; rowIndex++) {
//     if (board[rowIndex][col] === val) return false;
//   }
//   // 横向检查
//   for (let colIndex = 0; colIndex < n; colIndex++) {
//     if (board[row][colIndex] === val) return false;
//   }
//   // 九宫格检查
//   const startX = Math.floor(col / 3) * 3;
//   const startY = Math.floor(row / 3) * 3;
//   for (let rowIndex = startY; rowIndex < startY + 3; rowIndex++) {
//     for (let colIndex = startX; colIndex < startX + 3; colIndex++) {
//       if (board[rowIndex][colIndex] === val) return false;
//     }
//   }
//   return true;
// };

// /** 解数独
//  * 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。
//  * 数字 1-9 在每一列只能出现一次。
//  * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
//  * @param board 9*9格子
//  */
// export const solveSudoku = (board: string[][]): void => {
//   let n: number = 9;
//   backTracking(n, board);
//   function backTracking(n: number, board: string[][]): boolean {
//     for (let row = 0; row < n; row++) {
//       for (let col = 0; col < n; col++) {
//         if (board[row][col] === ".") {
//           for (let i = 1; i <= n; i++) {
//             if (isValid(col, row, String(i), board)) {
//               board[row][col] = String(i);
//               if (backTracking(n, board) === true) return true;
//               board[row][col] = ".";
//             }
//           }
//           return false;
//         }
//       }
//     }
//     return true;
//   }
// };
export const sudokuSolver = (matrix: number[][]): number[][] | string => {
  if (solveSudoku(matrix)) {
    return matrix;
  }
  return "此问题无解";
};

const UNASSIGNED = 0;

/** 解数独
 *
 * @param matrix
 * @returns
 */
const solveSudoku = (matrix: number[][]) => {
  // 辅助变量用于描述数独的行和列
  let row: number;
  let col = 0;
  // 检查格子是否为空
  let checkBlankSpaces = false;
  // 寻找空格子
  for (row = 0; row < matrix.length; row++) {
    for (col = 0; col < matrix[row].length; col++) {
      // 检测到空格子，终止内层循环
      if (matrix[row][col] === UNASSIGNED) {
        checkBlankSpaces = true;
        break;
      }
    }
    // 格子为空终止外层循环
    if (checkBlankSpaces) {
      break;
    }
  }
  // 格子不为空时终止递归
  if (!checkBlankSpaces) {
    return true;
  }
  // 为空格子填充数字，判断其是否满足数独的填充规则
  for (let num = 1; num <= 9; num++) {
    // 如果满足规则，就往空格子填充num
    if (matrixIsSafe(matrix, row, col, num)) {
      matrix[row][col] = num;
      // 递归，继续寻找空格子，然后填充
      if (solveSudoku(matrix)) {
        return true;
      }
      // 所有数字都尝试完后，仍然不满足则填充0
      matrix[row][col] = UNASSIGNED;
    }
  }
  // 回溯，即将返回到上一个递归栈
  return false;
};

/**校验当前值是否冲突
 *
 * @param matrix
 * @param row
 * @param col
 * @param num
 * @returns
 */
export const matrixIsSafe = (
  matrix: number[][],
  row: number,
  col: number,
  num: number
): boolean => {
  // 当num的值不再当前行，不在当前列，不在3*3的小格子中时则表示num不冲突
  return (
    !usedInRow(matrix, row, num) &&
    !usedInCol(matrix, col, num) &&
    !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
  );
};

/**检测当前值是否在矩阵的指定行中
 *
 * @param matrix
 * @param row
 * @param num
 * @returns
 */
const usedInRow = (matrix: number[][], row: number, num: number): boolean => {
  for (let col = 0; col < matrix.length; col++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
};

/**检测当前值是否在矩阵的指定列中
 *
 * @param matrix
 * @param col
 * @param num
 * @returns
 */
const usedInCol = (matrix: number[][], col: number, num: number): boolean => {
  for (let row = 0; row < matrix.length; row++) {
    if (matrix[row][col] === num) {
      return true;
    }
  }
  return false;
};

/**检测当前值是否在3*3的小矩阵中
 *
 * @param matrix
 * @param boxStartRow
 * @param boxStartCol
 * @param num
 * @returns
 */
const usedInBox = (
  matrix: number[][],
  boxStartRow: number,
  boxStartCol: number,
  num: number
): boolean => {
  for (let row = 0; row < 3; row++) {
    for (let col = 0; col < 3; col++) {
      if (matrix[row + boxStartRow][col + boxStartCol] === num) {
        return true;
      }
    }
  }
  return false;
};
enum DifficultyLevel {
  Simple = 28,
  easy = 30,
  difficult = 20,
}
export class Sudoku {
  private difficultyLevel: DifficultyLevel;
  sudokuGrid: number[][];
  constructor(difficultyLevel: DifficultyLevel = DifficultyLevel.Simple) {
    this.difficultyLevel = difficultyLevel;

    this.sudokuGrid = new Array<number>(9)
      .fill(0)
      .map(() => new Array<number>(9).fill(0));
  }

  /**初始化 */
  init() {
    /**二维数组初始化 */
    // const matrix: number[][] =
    // const matrix2: number[][] = Array.from(new Array(9).fill(0), () =>
    //   new Array(9).fill(0)
    // );
    const indexSet = new Set<number>();
    while (indexSet.size < this.difficultyLevel) {
      const num = Math.floor(Math.random() * (9 * 9));
      indexSet.add(num);
    }

    for (let val of indexSet) {
      const row = Math.floor(val / 9);
      const col = val % 9;
      while (true) {
        const n = Math.floor(Math.random() * 9) + 1;
        if (Sudoku.matrixIsValid(this.sudokuGrid, row, col, n)) {
          this.sudokuGrid[row][col] = n;
          break;
        }
      }
    }
  }

  static matrixIsValid = (
    matrix: number[][],
    row: number,
    col: number,
    num: number
  ): boolean => {
    // 当num的值不再当前行，不在当前列，不在3*3的小格子中时则表示num不冲突
    return (
      !Sudoku.rowIsValid(matrix, row, num) &&
      !Sudoku.colIsValid(matrix, col, num) &&
      !Sudoku.boxIsValid(matrix, row - (row % 3), col - (col % 3), num)
    );
  };

  //#region private method
  private static rowIsValid = (
    matrix: number[][],
    row: number,
    num: number
  ): boolean => {
    for (let col = 0; col < matrix.length; col++) {
      if (matrix[row][col] === num) {
        return true;
      }
    }
    return false;
  };

  private static colIsValid = (
    matrix: number[][],
    col: number,
    num: number
  ): boolean => {
    for (let row = 0; row < matrix.length; row++) {
      if (matrix[row][col] === num) {
        return true;
      }
    }
    return false;
  };

  /**检测当前值是否在3*3的小矩阵中
   *
   * @param matrix
   * @param boxStartRow
   * @param boxStartCol
   * @param num
   * @returns
   */
  private static boxIsValid = (
    matrix: number[][],
    boxStartRow: number,
    boxStartCol: number,
    num: number
  ): boolean => {
    for (let row = 0; row < 3; row++) {
      for (let col = 0; col < 3; col++) {
        if (matrix[row + boxStartRow][col + boxStartCol] === num) {
          return true;
        }
      }
    }
    return false;
  };
  //#endregion
}

// export function generateSudoku(size: number = 9): number[][] {
//   const sudoku: number[][] = Array.from({ length: size }, () =>
//     Array(size).fill(0)
//   );
//   // 初始化一个size*size的数组，每个元素都是0
//   for (let i = 0; i < size; i++) {
//     for (let j = 0; j < size; j++) {
//       sudoku[i][j] = i * size + j + 1;
//     }
//   }
//   // 随机生成size*size*4个数字，每个数字都是1-size*size*4之间的数字
//   for (let k = 0; k < size * size * 4; k++) {
//     const i = Math.floor(Math.random() * size);
//     const j = Math.floor(Math.random() * size);
//     const temp = sudoku[i][j];
//     sudoku[i][j] =
//       sudoku[Math.floor(Math.random() * size)][
//         Math.floor(Math.random() * size)
//       ];
//     sudoku[Math.floor(Math.random() * size)][Math.floor(Math.random() * size)] =
//       temp;
//   }
//   // 返回一个size*size的数组
//   return sudoku;
// }

// const sudoku = generateSudoku();
// console.log(sudoku);
